/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 07 - 18
 * Time: 13:27
 */
//力扣105.从前序与中序遍历序列构造二叉树
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;}
}
class Solution3 {
    int preIndex;//因为要用到递归，而前序遍历下标要不断往后走，所以前序遍历下标要定义为成员变量，所以buildTreeF传参时不需要传preIndex了
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeF(preorder, inorder, 0, inorder.length - 1);
    }
    private TreeNode buildTreeF(int[] preorder, int[] inorder, int ib, int ie) {
        if(ib > ie) {//这个条件加在这里
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int inIndex = find(inorder, ib, ie, preorder[preIndex]);
        preIndex++;
        //因为在前序遍历序列中preIndex是自增，所以创建的顺序是先创建根，再创建左树，后创建右树
        root.left = buildTreeF(preorder, inorder, ib, inIndex - 1);//注意是赋给root.left
        root.right = buildTreeF(preorder, inorder, inIndex + 1, ie);//注意是赋给root.right
        return root;
    }
    private int find(int[] inorder, int ib, int ie, int key) {
        for(int i = 0; i <= ie; i++) {//条件是<=，因为buildTreeF传ie的时候传的是inorder.length-1
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}


